package offer

import (
	. "GoLeetcode/common"
)

/*f1
时间复杂度:O(N)
空间复杂度:O(N)
*/

func rob(nums []int) int {
	n := len(nums)
	dp := make([]int, n+1)
	dp[1] = nums[0]
	for i := 2; i <= n; i++ {
		// 这里可能会有疑惑:如果第i个没有取,dp[i]=dp[i-1]好像不对,因为dp[i-1]第i-1个物品可能没有取,则实际上dp[i]=dp[i-1]+nums[i-1]
		// 解惑:假设第i-1没有取,则dp[i-1]其实是由dp[i-2]转移而来(dp[i-1]=dp[i-2]),所以此时dp[i]=dp[i-2]+nums[i-1]
		dp[i] = Max(dp[i-1], dp[i-2]+nums[i-1])
	}
	return dp[n]
}

/*f2
时间复杂度:O(N)
空间复杂度:O(1)
*/

func rob1(nums []int) int {
	// cur, pre对应当前层的dp[i], dp[i-1]
	// 当前层的cur对应上一层的dp[i-1], 当前层的pre对应上一层的dp[i-2]
	cur, pre := 0, 0
	for _, v := range nums {
		cur, pre = Max(pre+v, cur), cur
	}
	return cur
}
